package leetcode.editor.cn;

import java.util.*;

public class _236_LowestCommonAncestorOfABinaryTree {
    public static void main(String[] args) {
        Solution solution = new _236_LowestCommonAncestorOfABinaryTree().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    // 后序遍历
    class Solution {
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null || root == p || root == q) {
                return root;
            }
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            // 情况 1
            if (left != null && right != null) {
                return root;
            }
            // 情况 2
            if (left == null && right == null) {
                return null;
            }
            // 情况 3
            return left == null ? right : left;

        }
    }

    // Map + Set
    class Solution1 {
        Map<Integer, TreeNode> parent = new HashMap<>();
        Set<Integer> visited = new HashSet<>();

        public void dfs(TreeNode root) {
            if (root.left != null) {
                parent.put(root.left.val, root);
                dfs(root.left);
            }
            if (root.right != null) {
                parent.put(root.right.val, root);
                dfs(root.right);
            }
        }

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            dfs(root);
            while (p != null) {
                visited.add(p.val);
                p = parent.get(p.val);
            }
            while (q != null) {
                if (visited.contains(q.val)) {
                    return q;
                }
                q = parent.get(q.val);
            }
            return null;
        }
    }

    // 回溯算法
    class Solution3 {
        List<TreeNode> path = new ArrayList<>();
        List<TreeNode> p1 = null;
        List<TreeNode> p2 = null;
        int count = 0;

        private void preOrderedTraversal(TreeNode node, TreeNode p, TreeNode q) {
            if (count == 2 || node == null) {
                return;
            }
            path.add(node);
            if (node == p) {
                p1 = new ArrayList<>(path);
                count++;
            }
            if (node == q) {
                p2 = new ArrayList<>(path);
                count++;
            }
            if (count == 2) {
                return;
            }
            preOrderedTraversal(node.left, p, q);
            if (count == 2) {
                return;
            }
            preOrderedTraversal(node.right, p, q);
            if (count == 2) {
                return;
            }
            path.remove(path.size() - 1);
        }

        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            preOrderedTraversal(root, p, q);
            int idx = 0;
            while (idx < p1.size() && idx < p2.size() && p1.get(idx).equals(p2.get(idx))) {
                idx++;
            }
            return p1.get(idx - 1);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}